iT邦幫忙

2024 iThome 鐵人賽

DAY 26
0

2024/09/26 Leetcode Daily Problem

729. My Calendar I
難度: 中等

題意

實作一個MyCalendar的類,包含以下操作

  1. MyCalendar()初始化這個類
  2. boolean book(int start, int end),插入左閉右開區間時間段[start, end),並回傳true;若此時間段與已插入的時間段重疊則回傳false

思路

每插入一個時間段就按照其start排序好,接著每插入的的新時間段[start, end)

  1. 查詢排在start之後的第一個時間段lower_bound,檢查lower_boundstart是否與新時間段end重疊。若重疊則直接回傳false。
  2. 查詢lower_bound的前一個時間段prev,檢查prevend是否與新時間段start重疊。若重疊則直接回傳false。
  3. lower_bound, prev不存在,或前兩點都沒有重疊,則插入新時間段,回傳true。

實作

優先挑選能插入後自動排序的資料結構(std::set<pair<int, int>>map<int, int>)
並用二分搜的技巧搜尋到lower_bound
這裡主要是邊查邊學std::map::lower_bound(k)這個operator。

class MyCalendar
{
private:
    // Start -> End
    map<int, int> mp;

public:
    MyCalendar()
    {
        mp = map<int, int>{};
    }

    bool book(int start, int end)
    {
        // Returns an iterator pointing to the first element 
        // in the container whose key is not considered to go before k
        map<int, int>::iterator key_lower_it = mp.lower_bound(start);
        
        // Check overlap
        if (key_lower_it != mp.end() && key_lower_it->first < end)
            return false;
        if (key_lower_it != mp.begin() && prev(key_lower_it)->second > start)
            return false;

        mp[start] = end;
        return true;
    }
};

分析

若book次數為N。
根據std::map::insert(),每次O(logN)。
根據std::map::lower_bound(),每次O(logN)。
時間複雜度: O(NlogN),插入N個,二分搜N次。
空間複雜度: O(N),共N對start->end。

結果

Accepted
107/107 cases passed (68 ms)
Your runtime beats 88.62 % of cpp submissions
Your memory usage beats 59.1 % of cpp submissions (42.7 MB)

總結

Time Submitted Status Runtime Memory Language
09/26/2024 22:35 Accepted 68 ms 42.7 MB cpp

上一篇
[9/25] 所有前綴出現的次數
下一篇
[9/27] 插入區間II
系列文
菜就多練,不會就多刷31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言